package com.cdream.basic.algorithm.leetcode.array;

/**
 * @author cdream
 * @date 2021/10/19
 */
public class Question211 {

    class WordDictionary {
        Trie trie;

        public WordDictionary() {
            trie = new Trie();
        }

        public void addWord(String word) {
            trie.insert(word);
        }

        public boolean search(String word) {
            return dfs(word, 0, trie);
        }

        private boolean dfs(String word, int index, Trie trie) {
            if (index == word.length()) {
                return trie.isEnd;
            }
            char c = word.charAt(index);
            if (c == '.') {
                Trie[] children = trie.children;
                for (int i = 0; i < 26; i++) {
                    Trie child = children[i];
                    if (child != null && dfs(word, index + 1, child)) {
                        return true;
                    }
                }
            } else {
                Trie[] children = trie.children;
                Trie child = children[c - 'a'];
                if (child != null && dfs(word, index + 1, child)) {
                    return true;
                }

            }
            return false;
        }


    }

    class Trie {
        public Trie[] children;
        public boolean isEnd;

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            Trie cur = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int index = c - 'a';
                Trie child = cur.children[index];
                if (child == null) {
                    cur.children[index] = new Trie();
                }
                cur = cur.children[index];
            }
            cur.isEnd = true;

        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            Trie trie = getByPrefix(word);
            return trie != null && trie.isEnd;
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            return getByPrefix(prefix) != null;
        }

        private Trie getByPrefix(String pre) {
            Trie trie = this;
            for (int i = 0; i < pre.length(); i++) {
                char c = pre.charAt(i);
                int index = c - 'a';
                trie = trie.children[index];
                if (trie == null) {
                    return null;
                }
            }
            return trie;
        }
    }

}

